import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-10-09
 * Time: 21:27
 */

public class MyStack {
    class ListNode{
        private int value;
        private ListNode next;
    }
    private int[] elem;
    private int usedSize;
    public MyStack(){
        this.elem = new int[10];
    }
    public void show(){
        for (int i = 0; i < this.usedSize; i++){
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
    //1.链表逆序打印
    //递归
    public void show1(ListNode head){
        if (head != null){
            show1(head.next);
            System.out.print(head.value + " ");
        }
    }
    public void show2(ListNode head){
        if (head == null){
            return;
        }
        if (head.next == null){
            System.out.println(head.value);
            return;
        }
        show2(head.next);
        System.out.println(head.value);
    }
    //循环
    public void show3(ListNode head){
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        //将节点放到栈中
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //将节点一个一个出栈
        while (!stack.empty()){
            ListNode node = stack.pop();
            System.out.println(node.value);
        }
    }
    //逆波兰表达式计算
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")) {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (tokens[i]) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }
    //括号匹配问题
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        //遍历字符串
        for (int i = 0; i < s.length(); i++){
            //判断是否为左括号
            if (s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '('){
                //左括号压栈
                stack.push(s.charAt(i));
            }else{
                //判断是否栈空了但是字符串没有遍历完
                if (stack.empty()){
                    return false;
                }
                //匹配有括号
                char a = stack.pop();
                switch(s.charAt(i)){
                    case '}':
                        if (a != '{'){
                            return false;
                        }
                        break;
                    case ']':
                        if (a != '['){
                            return false;
                        }
                        break;
                    case ')':
                        if (a != '('){
                            return false;
                        }
                        break;
                }
            }
        }
        //判断是否字符串遍历完，栈还没空
        if (!stack.empty()){
            return false;
        }
        return true;
    }
    //栈的压入和弹出序列
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int l = pushV.length;
        int i = 0;
        int j = 0;
        while(i < l){
            stack.push(pushV[i]);
            while(!stack.empty() && j < l && stack.peek() == popV[j]){
                stack.pop();
                j++;
            }
            i++;
        }
        return stack.empty();
    }

    //1.压栈
    public void push(int value){
        if (this.elem.length == this.usedSize){
            this.elem = Arrays.copyOf(this.elem, this.usedSize * 2);
        }
        this.elem[usedSize] = value;
        usedSize ++;
    }
    //2.判空
    public boolean empty(){
        return this.usedSize == 0;
    }
    //3.出栈
    public int pop(){
        if (empty()){
            throw new StackEmptyException("栈为空！！！");
        }
        int a = this.elem[this.usedSize -1];
        usedSize--;
        return a;
    }
    //4.获取栈顶数据
    public int peek(){
        if (empty()){
            throw new StackEmptyException("栈为空！！！");
        }
        return this.elem[this.usedSize - 1];
    }
    //5.获取栈的数据个数
    public int size(){
        return this.usedSize;
    }
}
